#include <iostream> 
using namespace std;
int find_dest(int k, int *coin, int n)
{
	int * minCoin = new int[k + 1]();
	int * valueCoin = new int[k + 1]();
	memset(minCoin, 0, sizeof(int)*(k + 1));
	memset(valueCoin, 0, sizeof(int)*(k + 1));
	for (int i = 1; i <= k; i++)
	{
		int maxCoin = i;
		int value = 0;
		for (int j = 0; j < n; j++)
		{
			if (i >= coin[j])
			{
				if (minCoin[i - coin[j]] + 1 <= maxCoin && (i==coin[j]||valueCoin[i - coin[j]] != 0))//检测上一个是否有效，无效则跳过
				{
					maxCoin = minCoin[i - coin[j]] + 1;   //F[I] = MIN{F[I-VALUE[J]]+1
					value = coin[j];
				}
			}
		}
		minCoin[i] = maxCoin;
		valueCoin[i] = value;
	}
	if (valueCoin[k] != 0)
	{
		while (k)
		{
			cout << valueCoin[money] << ",";
			money -= valueCoin[money];
		}
		cout << endl;
	}
	else
	{
		cout << "不能支付"<< endl;
	}
	delete[] minCoin;
	delete[] valueCoin;
	return 0;
}
int main()
{
	int k = 569;//自己设定的一个k的数值
	int coin[7] = { 1,2,5,10,20,50,100};//各种面值
	find_dest(k, coin, 7);
	system("pause");
	return 0;
}
